package com.demo.example.hot100;

import java.util.ArrayList;
import java.util.List;

public class CombinationSum {
    public static List<List<Integer>> combinationSum(int[] candidates,int target){
        List<List<Integer>> res=new ArrayList<>();
        List<Integer> list=new ArrayList<>();
        process(candidates,0,target,res,list);
        return res;
    }
    public static void process(int[] candidates,int index,int target,List<List<Integer>> res,List<Integer> list){
        if(index==candidates.length){
            return;
        }
        if(target==0){
            res.add(list);
            return;
        }
        process(candidates,index+1,target,res,list);
        //选择当前数
        if(target-candidates[index]>=0){
            list.add(candidates[index]);
            process(candidates,index,target-candidates[index],res,list);
            list.remove(list.size()-1);
        }
    }
    public static int findTheSum(List<Integer> list){
        int sum=0;
        for(int i:list){
            sum+=i;
        }
        return sum;
    }
}
